package com.hanxiaozhang.windowandmonotonestack;

import java.util.Stack;

/**
 * 功能描述: <br>
 * 〈〉
 * <p>
 * 给定一个只包含正数的数组arr，arr中任何一个子数组sub，一定都可以算出(sub累加和 )* (sub中的最小值)是什么，
 * 那么所有子数组中，这个值最大是多少？
 *
 * @Author: hanxinghua
 * @Date: 2024/1/25
 */
public class No4AllTimesMinToMax {

    public static void main(String[] args) {
        int testTimes = 2000000;
        System.out.println("test begin");
        for (int i = 0; i < testTimes; i++) {
            int[] arr = generateRandomArray();
            if (method1(arr) != method2(arr)) {
                System.out.println("FUCK!");
                break;
            }
        }
        System.out.println("test finish");
    }


    /**
     * 方法1
     * 笨方法
     *
     * @param arr
     * @return
     */
    public static int method1(int[] arr) {
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < arr.length; i++) {
            for (int j = i; j < arr.length; j++) {
                int minNum = Integer.MAX_VALUE;
                int sum = 0;
                for (int k = i; k <= j; k++) {
                    // 子数组求和
                    sum += arr[k];
                    // 最小值
                    minNum = Math.min(minNum, arr[k]);
                }
                // 获取最大值
                max = Math.max(max, minNum * sum);
            }
        }
        return max;
    }


    /**
     * 方法2
     * 使用单调栈
     *
     * @param arr
     * @return
     */
    public static int method2(int[] arr) {
        int size = arr.length;
        // 构建出0开始到索引位置的累加和的数组
        int[] sums = new int[size];
        sums[0] = arr[0];
        for (int i = 1; i < size; i++) {
            sums[i] = sums[i - 1] + arr[i];
        }
        int max = Integer.MIN_VALUE;
        // 栈中：底->顶，即小->大 ，栈中记录是 索引位置
        Stack<Integer> stack = new Stack();
        // 循环元素，插入单调栈中 -> 进栈
        for (int i = 0; i < size; i++) {
            // 栈部不为空 && 栈顶元素 >= arr[i]，弹出所有比arr[i]大的元素，即当前arr[i]是最小
            while (!stack.isEmpty() && arr[stack.peek()] >= arr[i]) {
                // 弹出栈顶元素
                int j = stack.pop();
                // 栈为空：sum = sums[i - 1]
                // 栈不为空：sum = sums[i - 1] - sums[stack.peek()]
                max = Math.max(max, (stack.isEmpty() ? sums[i - 1] : (sums[i - 1] - sums[stack.peek()])) * arr[j]);
            }
            // 插入到栈中
            stack.push(i);
        }
        // 栈不为空
        while (!stack.isEmpty()) {
            int j = stack.pop();
            max = Math.max(max, (stack.isEmpty() ? sums[size - 1] : (sums[size - 1] - sums[stack.peek()])) * arr[j]);
        }
        return max;
    }


    public static int[] generateRandomArray() {
        int[] arr = new int[(int) (Math.random() * 20) + 10];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = (int) (Math.random() * 101);
        }
        return arr;
    }

}
